import random
import copy
import operator
import defaultvalue
##################################################
# Genome Structure
##################################################
class SGenome:
    def __init__(self,fitness=0,weights=[]):
        self.fitness=fitness
        self.vec_weights=copy.deepcopy(weights)

    def set_fitness(self,fitness):
        self.fitness=fitness

    def __lt__(self,genome):
        """ compare which son is better """
        return self.fitness < genome.fitness
    
##################################################
# randomize direction, with controlled trends 
##################################################
class CGenAlg:
    def __init__(self,popsize,mut_rate,cross_rat,numweights):
        self.pop_size=popsize # num of sons
        self.mutation_rate=mut_rate # mutate rate
        self.crossover_rate=cross_rat # cross rate
        self.chromo_length=numweights # length of each routel
        self.total_fitness=0
        self.m_cGeneration=0
        self.vec_pop=[]
        # randomize a route
        for i in xrange(self.pop_size):
            self.vec_pop.append(SGenome())
            for j in xrange(self.chromo_length):
                self.vec_pop[i].vec_weights.append(random.randint(1 , 4))

    def mutate(self,chromo):
        """ try to mutate a route """
        for i in xrange(len(chromo)):
            if random.uniform(0,1) < self.mutation_rate:
                chromo[i]=(chromo[i]+random.randint(-1,1)*defaultvalue.dMaxPerturbation)%4 + 1

    def get_chromo(self):
        """ get a son """
        slice=random.uniform(0,1)*self.total_fitness # get a alice quantity
        chosen_one=SGenome()
        fitness_now=0
        for i in xrange(self.pop_size):
            fitness_now = FitnessSoFar+self.vec_pop[i].fitness
            if fitness_now > slice: # more than the slice, then return
                chosen_one=copy.deepcopy(self.vec_pop[i])
        return TheChosenOne

    def cross_over(self,mum,dad,baby1,baby2):
        """ try to cross over two route """
        if len(mum) != len(dad) or len(mum) != self.chromo_length: # invalid route
            return
        # do not cross over
        if random.uniform(0,1) > self.crossover_rate or operator.eq(mum,dad): 
            for i in xrange(len(dad)):
                baby1.append(mum[i])
                baby2.append(dad[i])
            return
        # cross over
        cp=random.randint(0,self.chromo_length-1) # choose a cross point
        for i in xrange(cp):
            baby1.append(mum[i])
            baby2.append(dad[i])
        for i in xrange(cp,self.chromo_length):
            baby1.append(dad[i])
            baby2.append(mum[i])
        return

    def start(self ,map , start_position, destination):
        """ init the algorithm """
        self.map = map
        self.s_position = start_position
        self.destination = destination
        self.length=len(map)
        self.height = len(map[0])
        # init each route's fitness
        for i in xrange(self.pop_size):            
            self.vec_pop[i].fitness = defaultvalue.startFitness
            self.total_fitness += defaultvalue.startFitness

    def calculate_fit(self):
        """ calulate a route's score """
        self.total_fitness = 0
        for index in xrange(self.pop_size):
            route = 0
            i = self.s_position[0]
            j = self.s_position[1]
            # try to walk along a route
            for k in xrange(self.chromo_length):
                route += 1
                if self.vec_pop[index].vec_weights[k] == 1:
                    if i - 1 >= 0 and self.map[i-1][j]==0:
                        i -= 1
                if self.vec_pop[index].vec_weights[k] == 2:
                    if j - 1 >= 0 and self.map[i][j-1] == 0:
                        j -=1
                if self.vec_pop[index].vec_weights[k] == 3:
                    if i + 1 < self.length and self.map[i+1][j] == 0:
                        i += 1
                if self.vec_pop[index].vec_weights[k] == 4:
                    if j + 1 < self.height and self.map[i][j+1] == 0:
                        j +=1
                if i == self.destination[0] and j == self.destination[1]:
                    break
            # if reach the destination or its near areas, it will get a high score 
            fitChanged = 2 - operator.abs(self.destination[0] - i)/self.length \
                         - operator.abs(self.destination[1] - j)/self.height
            fitChanged += (1 - route/self.chromo_length)
            self.vec_pop[index].fitness += fitChanged
            self.total_fitness += self.vec_pop[index].fitness

    def epoch(self):
        """ find a new series of route """
        self.vec_pop.sort() # sort the routes
        vecNewPop=[]
        # get needs amount of routes
        while len(vecNewPop) < self.pop_size :
            # get two parents
            mum=self.get_chromo()
            dad=self.get_chromo()
            baby1=[]
            baby2=[]
            # produce two sons
            self.cross_over(mum.vec_weights,dad.vec_weights,baby1,baby2)
            # mutate either son
            self.mutate(baby1)
            self.mutate(baby2)
            vecNewPop.append(SGenome(0,baby1))
            # if get needed amount 
            if len(vecNewPop)==self.pop_size :
                break
            else:
                vecNewPop.append(SGenome(0,baby2))
        self.vec_pop=copy.deepcopy(vecNewPop)      

    def search(self, map , start_position, destination):
        self.start(map , start_position, destination)
        times = 0
        # find new routes for 20 times
        while times < 20:
            self.calculate_fit()
            self.epoch()
            times += 1
        self.vec_pop.sort()
        finalroute = []
        i = self.s_position[0]
        j = self.s_position[1]
        # eliminate invalid steps from the route
        for k in xrange(self.chromo_length):
            if self.vec_pop[0].vec_weights[k] == 1:
                if i - 1 > 0 and self.map[i-1][j]==0:
                    i -= 1
                    finalroute.append(self.vec_pop[0].vec_weights[k] - 1)                    
            if self.vec_pop[0].vec_weights[k] == 2:
                if j - 1 > 0 and self.map[i][j-1] == 0:
                    j -=1
                    finalroute.append(self.vec_pop[0].vec_weights[k] - 1)                    
            if self.vec_pop[0].vec_weights[k] == 3:
                if i + 1 < self.length and self.map[i+1][j] == 0:
                    i += 1
                    finalroute.append(self.vec_pop[0].vec_weights[k] - 1)
            if self.vec_pop[0].vec_weights[k] == 4:
                if j + 1 < self.height and self.map[i][j+1] == 0:
                    j +=1
                    finalroute.append(self.vec_pop[0].vec_weights[k] - 1)
            if i == self.destination[0] and j == self.destination[1]:
                    break
        return finalroute
